#!/usr/bin/env python

import string
import re

""" http://en.wikipedia.org/wiki/Levenshtein_distance

    Levenshtein distance is a metric for measuring the amount of difference between two sequences (i.e., the so called edit distance). 
    The Levenshtein distance between two strings is given by the minimum number of operations needed to transform one string into the other, 
    where an operation is an insertion, deletion, or substitution of a single character.

    The Levenshtein distance has several simple upper and lower bounds that are useful 
    in applications which compute many of them and compare them. These include:
    * It is always at least the difference of the sizes of the two strings.
    * It is at most the length of the longer string.
    * It is zero if and only if the strings are identical.
    * If the strings are the same size, the Hamming distance is an upper bound on the Levenshtein distance.
"""
## optional implementations of Levenshtein distance
# ld1 http://www.poromenos.org/node/87
# ld3 http://code.activestate.com/recipes/576874/

def ld_hetland_org(a,b):
    """ Calculates the Levenshtein distance between a and b.
    
    http://hetland.org/coding/python/levenshtein.py
    """ 
    n, m = len(a), len(b)
    if n > m:
        # Make sure n <= m, to use O(min(n,m)) space
        a,b = b,a
        n,m = m,n
        
    current = range(n+1)
    for i in range(1,m+1):
        previous, current = current, [i]+[0]*n
        for j in range(1,n+1):
            add, delete = previous[j]+1, current[j-1]+1
            change = previous[j-1]
            if a[j-1] != b[i-1]:
                change = change + 1
            current[j] = min(add, delete, change)
            
    return current[n]

def main(a, b):
    return ld_hetland_org(a, b)

if __name__ == '__main__':
    pass
